package com.baixiaowen.xiaoaointerview.Java编程功底篇.五种手写排序.快速排序;

import com.baixiaowen.xiaoaointerview.Java编程功底篇.五种手写排序.IIMutableSorter;

import java.util.List;
import java.util.stream.Collectors;
import static java.util.stream.Collectors.toList;

/**
 * 快速排序 第一版
 *
 * @author Baixiaowen
 */
public class QuickSortV1 implements IIMutableSorter {

    @Override
    public List<Integer> sort(List<Integer> A) {
        return this.quickSort(A);
    }

    private List<Integer> quickSort(List<Integer> A) {

        if (A.size() <= 1) {
            return A;
        }

        // |---left---| x |---right---||
        Integer x = A.get(0);
        List<Integer> left = A.stream().filter(a -> a < x).collect(Collectors.toList());
        List<Integer> mid = A.stream().filter(a -> a.equals(x)).collect(Collectors.toList());
        List<Integer> right = A.stream().filter(a -> a > x).collect(toList());

        left = quickSort(left);
        right = quickSort(right);
        left.addAll(mid);
        left.addAll(right);
        return left;
    }
}
